#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int start_i, start_j;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    start_i = i;
                    start_j = j;
                }
            }
        }
        return dfs(grid, start_i, start_j);
    }
private:
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int n = grid.size();
        int m = grid[0].size();
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == -1) { return 0; }
        if (grid[i][j] == 2) { if (nozero(grid)) { return 1; }return 0; }
        int temp = grid[i][j];
        grid[i][j] = -1;
        int path = dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
        grid[i][j] = temp;
        return path;
    }
    bool nozero(vector<vector<int>>& grid) {
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 0) { return false; }
            }
        }
        return true;
    }
};

class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int starti,startj,empty = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) { starti = i, startj = j; }
                else if (grid[i][j] == 0) { empty++; }
            }
        }
        return dfs(grid, starti, startj, empty);
    }
private:
    int dfs(vector<vector<int>>& grid, int i, int j, int empty) {
        int n = grid.size();
        int m = grid[0].size();
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == -1) { return 0; }
        if (grid[i][j] == 2) { if (empty == 0) { return 1; }return 0; }
        int temp = grid[i][j];
        grid[i][j] = -1;
        empty--;
        int path = dfs(grid, i + 1, j, empty) + dfs(grid, i - 1, j, empty) + dfs(grid, i, j + 1, empty) + dfs(grid, i, j - 1, empty);
        grid[i][j] = temp;
        return path;

    }
};